"""
37. 解数独
困难
1.5K
相关企业
编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。



示例 1：


输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：


提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
"""

from typing import List


# 遍历全部格子
class Solution:
    # 生成了 10 * 9 的数据
    row_state = [[False for i in range(10)] for _ in range(9)]
    column_state = [[False for i in range(10)] for _ in range(9)]
    box_state = [[False for i in range(10)] for _ in range(9)]
    board = []

    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.row_state = [[False for i in range(10)] for _ in range(9)]
        self.column_state = [[False for i in range(10)] for _ in range(9)]
        self.box_state = [[False for i in range(10)] for _ in range(9)]
        self.board = board

        # 把输入的值，转换成 行列块的储存方式
        for i in range(9):
            for j in range(9):
                if self.board[i][j] != ".":
                    num = int(self.board[i][j])
                    self.row_state[i][num] = True
                    self.column_state[j][num] = True
                    self.box_state[(i // 3) * 3 + j // 3][num] = True

        # 递归计算空位的数字
        def recursive_place_number(self, row: int, column: int) -> bool:
            if row == -1 and column == -1:
                return True
            if board[row][column] != ".":
                return False

            for i in range(1, 10):
                if (
                        self.row_state[row][i]
                        or self.column_state[column][i]
                        or self.box_state[(row // 3) * 3 + column // 3][i]
                ):
                    continue
                else:
                    self.place_number(row, column, i)
                    x, y = self.get_max_possible_coordinate()
                    if recursive_place_number(self, x, y):
                        return True
                    self.undo_number_placement(row, column, i)
            return False

        x, y = self.get_max_possible_coordinate()
        recursive_place_number(self, x, y)

    # 填充字符
    def place_number(self, row: int, column: int, i: int) -> bool:
        self.row_state[row][i] = True
        self.column_state[column][i] = True
        self.box_state[(row // 3) * 3 + column // 3][i] = True
        self.board[row][column] = str(i)

    # 清除字符
    def undo_number_placement(self, row: int, column: int, i: int) -> bool:
        self.row_state[row][i] = False
        self.column_state[column][i] = False
        self.box_state[(row // 3) * 3 + column // 3][i] = False
        self.board[row][column] = "."

    def get_max_possible_coordinate(self) -> (int, int):
        x, y, min_count = -1, -1, 9
        for i in range(9):
            for j in range(9):
                if self.board[i][j] != ".":
                    continue
                tmp_count = 9
                for k in range(9):
                    if (
                            self.row_state[i][k]
                            or self.column_state[j][k]
                            or self.box_state[(i // 3) * 3 + j // 3][k]

                    ):
                        tmp_count -= 1
                if tmp_count == 1:
                    return i, j
                if min_count > tmp_count:
                    min_count = tmp_count
                    x = i
                    y = j
        return x, y


if __name__ == '__main__':
    board = [["5", "3", ".", ".", "7", ".", ".", ".", "."], ["6", ".", ".", "1", "9", "5", ".", ".", "."],
             [".", "9", "8", ".", ".", ".", ".", "6", "."], ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
             ["4", ".", ".", "8", ".", "3", ".", ".", "1"], ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
             [".", "6", ".", ".", ".", ".", "2", "8", "."], [".", ".", ".", "4", "1", "9", ".", ".", "5"],
             [".", ".", ".", ".", "8", ".", ".", "7", "9"]]
    solution = Solution()

    print(solution.solveSudoku(board))
